package com.wdc.回溯;


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.function.BinaryOperator;

public class E02Leetcode216 {
    private List<List<Integer>> result = new ArrayList<>();
    private LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {

        backtracking(k,n,1);
        return result;
    }

    void backtracking(int k, int n ,int startIndex){
        //结束条件
        if (path.size() == k){
            //先判断然后加入返回结果
            int sum = path.stream()
                    .reduce(0, Integer::sum);
            if (sum > n){
                return;
            }
            if (sum == n ){
                result.add(new ArrayList<>(path));
            }
            return;
        }

        for (int i = startIndex; i <= 9 - (k-path.size()) + 1; i++) {
            //处理节点
            path.add(i);
            //递归调用
            backtracking(k,n,i + 1);
            //回溯
            path.removeLast();
        }
    }



}
